/*
 * @Author: liusheng
 * @Date: 2022-06-12 19:08:21
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-12 22:54:04
 * @Description: 剑指 Offer II 078. 合并排序链表
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 * 剑指 Offer II 078. 合并排序链表
给定一个链表数组，每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中，返回合并后的链表。

 

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：

输入：lists = []
输出：[]
示例 3：

输入：lists = [[]]
输出：[]
 

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
 

注意：本题与主站 23 题相同： https://leetcode-cn.com/problems/merge-k-sorted-lists/

通过次数14,542  提交次数22,804
 */

#include "header.h"

struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

/*
时间复杂度:O(kn×logk)
空间复杂度：递归会使用到 O(log k) 空间代价的栈空间
*/
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergeSort(lists,0,lists.size() - 1);
    }
private:
    ListNode * mergeSort(vector<ListNode*>& lists,int left,int right)
    {
        if (left == right)
        {
            return lists[left];
        }
        else if(left > right)
        {
            return nullptr;
        }

        int mid = left + (right - left) / 2;

        ListNode * l1 = mergeSort(lists,left,mid);
        ListNode * l2 = mergeSort(lists,mid + 1,right);

        return merge(l1,l2);
    }

    ListNode * merge(ListNode * head1,ListNode * head2)
    {
        ListNode * dummyHead = new ListNode();
        ListNode * tail = dummyHead;
        while (head1 && head2)
        {
            if (head1->val < head2->val)
            {
                tail->next = head1;
                head1 = head1->next;
            }
            else
            {
                tail->next = head2;
                head2 = head2->next;
            }

            tail = tail->next;
        }

        tail->next = head1 ? head1 : head2;

        ListNode * newHead = dummyHead->next;
        delete dummyHead;
        return newHead;
    }
};

/*
priority_queue solution
*/
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto listNodeGrtCmp = [] (ListNode* l1,ListNode *l2)
        {
            return l1->val > l2->val;
        };

        priority_queue<ListNode*,vector<ListNode *>,decltype(listNodeGrtCmp)> smallHeadPQ(listNodeGrtCmp);
        for (auto head : lists)
        {
            if (head)
            {
                smallHeadPQ.push(head);
            }
        }
        ListNode * dummyHead = new ListNode();
        ListNode * tail = dummyHead;
        while (!smallHeadPQ.empty())
        {
            ListNode * node = smallHeadPQ.top();
            smallHeadPQ.pop();
            tail->next = node;
            tail = tail->next;
            if (node->next)
            {
                smallHeadPQ.push(node->next);
            }
        }

        ListNode * newHead = dummyHead->next;
        delete dummyHead;
        return newHead;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        struct nodeGrtCmp
        {
            bool operator ()(ListNode * l1,ListNode * l2)
            {
                return l1->val > l2->val;
            }
        };
        
        priority_queue<ListNode *,vector<ListNode *>,nodeGrtCmp> smallHeapPQ;
        for (auto head : lists)
        {
            if (head)
            {
                smallHeapPQ.push(head);
            }
        